package dp;

public class climbStairs {
    int total=0;
    //回溯超时2^n
    // public int climbStairs(int n) {
    //     backTrack(0, n);
    //     return total;
    // }
    // public void backTrack(int pos,int n){
    //     if (pos>n) {
    //         return; 
    //     }else if(pos==n){
    //         total++;
    //         return;
    //     }
    //     backTrack(pos+1, n);
    //     backTrack(pos+2, n);

    // }
    //还是超时 复杂度一样
    // public int climbStairs(int n) {
    //     // fn = fn-1+fn-2
        
    //     return dfs(n);
    // }
    // public int dfs(int n){
    //     if (n==1) {
    //         return 1;
    //     }else if(n==2){
    //         return 2;
    //     }else if(n<=0){
    //         return 0;
    //     }
    //     return dfs(n-1)+dfs(n-2);

    // }
    // public int climbStairs(int n) {
    //     int p=0,q=0,r=1;
    //     for(int i=1;i<=n;i++){
    //         p=q;
    //         q=r;
    //         r=p+q;
    //     }
    //     return r;
    // }
    public int climbStairs(int n) {
        if (n==1) {
            return 1;
        }else if(n==2){
            return 2;
        }
        int[][] dp=new int[2][n+1];
        //初始化
        dp[0][1]=1;
        dp[1][1]=0;
        dp[1][2]=1;
        for(int i=2;i<=n;i++){
            dp[0][i]=dp[0][i-1];
        }
        int[] weight = new int[]{1,2};
        for(int i=1;i<2;i++){
            for(int j=0;j<=n;j++){
                if(j<weight[i]){
                    dp[i][j]=dp[i-1][j];
                }else{
                    dp[i][j]=dp[i][j-weight[i]]+dp[i-1][j-weight[i-1]];
                }
            }
        }
        return dp[0][n]+dp[1][n];
    }
    public static void main(String[] args) {
        climbStairs obj = new climbStairs();
        int n=4;
        System.out.println(obj.climbStairs(n));
    }
}
